class Solution {
public:

    void print(vector<int> v) {
        for (auto& ele : v) 
            cout << ele << " ";
        cout << endl;
    }

    void permute(vector<vector<int>>& all_sol, vector<int>& nums, vector<int>& sol, vector<int>& book) {
        if (sol.size() == nums.size()) {
            all_sol.push_back(sol);
            print(sol);
            return;
        }

        for (int i = 0; i < nums.size(); i++) {
            if (book[i] == false) {
                sol.push_back(nums[i]);
                book[i] = true;
                permute(all_sol, nums, sol, book);
                book[i] = false;
                sol.pop_back();
            }
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> result;
        vector<int> book(nums.size(), false);
        vector<int> sol;
        
        permute(result, nums, sol, book);
        return result;
    }
};
